package xp.ass.imitate.algorithm.bitmap;

/**
 * @author chent3
 * @date 2024/10/11
 * <p>
 * int -> 8 bit ,
 * [2, 4, 5, 3, 0]
 * int -> bit[8]
 * <p>
 * 2 ->   express 0000 0100
 * 2 ,3   express 0000 1100
 * if this number exists , then bit[index] = 1
 */

/**
 * advantage :
 * 1. save memory， BitMap can use ont long express 64 numbers
 * <p>
 * disadvantage:
 * 2. 如果数据分布不均匀，则会造成空间的浪费
 */
public class BitMap {
    /**
     * int -> 8 bit -> can express 8 numbers
     */
    private long[] buckets;

    // 1 << 6 = 64
    private final byte bucketSize = 6;

    public BitMap() {
        // -1 : because the index start from 0
        buckets = new long[bucketIndex(Long.SIZE - 1) + 1];
    }

    public BitMap(int size) {
        if (size <= 0) {
            throw new IllegalArgumentException("size 必须大于 0");
        }
        buckets = new long[bucketIndex(size-1) + 1];
    }


    public void put(int bitIndex) {
        ensureCapacity(bitIndex);

        int bucketIndex = bucketIndex(bitIndex);

        buckets[bucketIndex] |= (1L << bitIndex);
    }

    public boolean get(int bitIndex) {
        int bucketIndex = bucketIndex(bitIndex);
        if (bucketIndex > buckets.length) {
            return false;
        }
        return ((buckets[bucketIndex]) & (1L << bitIndex)) != 0;
    }


    private void ensureCapacity(int bitIndex) {
        // one long can contain 64 number
        int bucketIndex = bucketIndex(bitIndex);

        if (bucketIndex >= buckets.length) {
            long[] expandedBuckets = new long[bucketIndex << 1];
            System.arraycopy(buckets, 0, expandedBuckets, 0, buckets.length);
            this.buckets = expandedBuckets;
        }
    }

    private int bucketIndex(int bitIndex) {
        return bitIndex >> bucketSize;
    }

    public int size() {
        return buckets.length;
    }

}
